local AStar = class("AStar")

function AStar:ctor(width, height)
	assert(width, "Width must not be nil")
	assert(width, "Height must not be nil")

	self._width = width
	self._height = height

	for i = 1, width * height do
		self[i] = {CanMove = false}
	end

	self._close_grids = {}
	self._open_grids = {}

	self._transverse_move = 10
	self._vertical_move = 10
	self._oblique_move = 14
	self._can_oblique = true
end

AStar.Direction = 
{
	kUP = "UP",
	kDown = "Down",
	kLeft = "Left",
	kRight = "Right",
	KLeftUP = "LeftUP",
	kLeftDown = "LeftDown",
	kRightUP = "RightUP",
	kRightDown = "RightDown",
}

function AStar:containGrid(list, pos)
	local contain = false

	for i,v in ipairs(list) do
		if v.x == pos.x and v.y == pos.y then
			contain = true
			break
		end
	end

	return contain
end

function AStar:getNearbyGrid(pos, direction)
	local value = nil

	if direction == AStar.Direction.kUP then
		if pos.y < self._height then
			value = {x = pos.x, y = pos.y + 1}
		end
	end
	if direction == AStar.Direction.kDown then
		if pos.y > 1 then
			value = {x = pos.x, y = pos.y - 1}
		end
	end
	if direction == AStar.Direction.kLeft then
		if pos.x > 1 then
			value = {x = pos.x - 1, y = pos.y}
		end
	end
	if direction == AStar.Direction.kRight then
		if pos.x < self._width then
			value = {x = pos.x + 1, y = pos.y}
		end
	end
	if self:getCanOblique() and direction == AStar.Direction.KLeftUP then
		if pos.y < self._height and pos.x > 1 then
			value = {x = pos.x - 1, y = pos.y + 1}
		end
	end
	if self:getCanOblique() and direction == AStar.Direction.kLeftDown then
		if pos.y > 1 and pos.x > 1 then
			value = {x = pos.x - 1, y = pos.y - 1}
		end
	end
	if self:getCanOblique() and direction == AStar.Direction.kRightUP then
		if pos.y < self._height and pos.x < self._width then
			value = {x = pos.x + 1, y = pos.y + 1}
		end
	end
	if self:getCanOblique() and direction == AStar.Direction.kRightDown then
		if pos.y > 1 and pos.x > self._width then
			value = {x = pos.x - 1, y = pos.y - 1}
		end
	end

	return value
end

function AStar:getNearbyCanMoveGrid(pos, direction)
	local value = self:getNearbyGrid(pos, direction)

	while true do		
		if not value then
			break
		end

		if not self:getGridCanMove(value) then
			value = nil
			break
		end

		if direction == "LeftDown" and not self:getGridCanMove(self:getNearbyGrid(pos, "Left")) and not self:getGridCanMove(self:getNearbyGrid(pos, "Down")) then
			value = nil
			break
		end
		if direction == "LeftUP" and not self:getGridCanMove(self:getNearbyGrid(pos, "Left")) and not self:getGridCanMove(self:getNearbyGrid(pos, "UP")) then
			value = nil
			break
		end
		if direction == "RightDown" and not self:getGridCanMove(self:getNearbyGrid(pos, "Right")) and not self:getGridCanMove(self:getNearbyGrid(pos, "Down")) then
			value = nil
			break
		end
		if direction == "RightUP" and not self:getGridCanMove(self:getNearbyGrid(pos, "Right")) and not self:getGridCanMove(self:getNearbyGrid(pos, "UP")) then
			value = nil
			break
		end

		break
	end

	return value
end

function AStar:getHValue(endpos, pos)
	return math.abs(pos.x - endpos.x) + math.abs(pos.y - endpos.y)
end

function AStar:getGValue(lastpos, pos)
	local lastoffset = self:getGridOffset(lastpos)
	local lastg = self[lastoffset].G

	local move = 0
	if lastpos.x == pos.x then
		move = self._transverse_move
	elseif lastpos.y == pos.y then
		move = self._vertical_move
	else
		move = self._oblique_move
	end

	return lastg + move
end

function AStar:setTransverseMove(v)
	self._transverse_move = v
end

function AStar:getTransverseMove()
	return self._transverse_move
end

function AStar:setVerticalMove(v)
	self._vertical_move = v
end

function AStar:getVerticalMove()
	return self._vertical_move
end

function AStar:setObliqueMove(v)
	self._oblique_move = v
end

function AStar:getObliqueMove()
	return self._oblique_move
end


function AStar:getGridOffset(pos)
	return pos.x + (pos.y - 1) * self._width
end

function AStar:setCanOblique(v)
	self._can_oblique = v
end

function AStar:getCanOblique()
	return self._can_oblique
end

function AStar:setGridCanMove(pos, canmove)
	local offset = self:getGridOffset(pos)
	self[offset].CanMove = canmove
end

function AStar:getGridCanMove(pos)
	local offset = self:getGridOffset(pos)
	local canmove = self[offset]

	assert(canmove ~= nil, "Error Postion {"..pos.x..", "..pos.y.."} should not be nil")

	return canmove.CanMove
end

function AStar:findOptimumSolution(path_, start_, endpos_)
	local change_pos = start_.x < endpos_.x or start_.y < endpos_.y

	local start, endpos = nil, nil
	if change_pos then
		start, endpos = endpos_, start_
	else
		start, endpos = start_, endpos_
	end

	local path = {}

	self._close_grids = {}
	self._open_grids = {}

	table.insert(self._open_grids, start)
	local startoffset = self:getGridOffset(start)
	self[startoffset].G = 0
	self[startoffset].F = self:getHValue(endpos, start)

	local types = {	"UP", "Down", "Left", "Right", "LeftUP", "LeftDown", "RightUP", "RightDown" }

	local function SubGrid(g1, g2)
		return {x = g1.x - g2.x, y = g1.y - g2.y}
	end

	local function GetOrientation(g1, g2)
		if not g1 or not g2 then
			return nil
		end

		local names = {}

		local offset = SubGrid(g2, g1)
		if offset.x > 0 then
			table.insert(names, "Right")
		elseif offset.x < 0 then
			table.insert(names, "Left")
		end

		if offset.y > 0 then
			table.insert(names, "UP")
		elseif offset.y < 0 then
			table.insert(names, "Down")
		end

		return table.concat(names)
	end

	local function GetOrientationIndex(orientation)
		local index = 999

		for i,v in ipairs(types) do
			if v == orientation then
				index = i
				break
			end
		end

		return index
	end

	local function HandleGrid(grid, orientation)
		local neargrids = self:getNearbyCanMoveGrid(grid, orientation)
	 	if neargrids and not self:containGrid(self._close_grids, neargrids) then
	 		local offset = self:getGridOffset(neargrids)

	 		local thisG = self:getGValue(grid, neargrids)

	 		-- print("Orientation", orientation, GetOrientation(neargrids, self[offset].Parent))

	 		if self:containGrid(self._open_grids, neargrids) then
		 		if self[offset].G > thisG or (self[offset].G == thisG and GetOrientationIndex(orientation) < GetOrientationIndex(GetOrientation(neargrids, self[offset].Parent))) then
		 			self[offset].G = thisG
		 			self[offset].F = thisG + self:getHValue(endpos, neargrids)
		 			self[offset].Parent = grid
		 		end
	 		else 
	 			self[offset].G = thisG
	 			self[offset].F = thisG + self:getHValue(endpos, neargrids)
	 			self[offset].Parent = grid
	 			table.insert(self._open_grids, neargrids)
	 		end
	 	end
	end

	while true do 
		if #self._open_grids == 0 then
			break
		end

		if self:containGrid(self._open_grids, endpos) then
			break
		end

		table.sort(self._open_grids, function(a, b) 
			local offseta = self:getGridOffset(a)
			local offsetb = self:getGridOffset(b)
			return self[offseta].F < self[offsetb].F 
		end)

		local this_grids = self._open_grids[1]
		table.remove(self._open_grids, 1)
		table.insert(self._close_grids, this_grids)

		for i,v in ipairs(types) do
		 	HandleGrid(this_grids, v)
		end
	end

	local offsettemp = self:getGridOffset(endpos)
	local temp = self[offsettemp]

	if temp.Parent then
		table.insert(path, endpos)
	end

	while true do
		if not temp.Parent then
			break
		end

		table.insert(path, temp.Parent)

		offsettemp = self:getGridOffset(temp.Parent)
		temp = self[offsettemp]
	end

	self._close_grids = {}
	self._open_grids = {}

	for i = 1, self._width * self._height do
		self[i].G = nil
		self[i].F = nil
		self[i].Parent = nil
	end

	if change_pos then
		for i = #path, 1, -1 do
			table.insert(path_, path[i])
		end
	else
		for i,v in ipairs(path) do
		 	table.insert(path_, v)
		 end 
	end
end

function AStar:debug(path, start, endpos)
	print("-------- AStar:debug --------")
	print("A:Start B:End *:CanNotMove -:CanMove +:ThePath")
	for j = 1, self._height do
		local line = ""
		for i = 1, self._width do
			-- line = line..j..(self:getGridCanMove({x = i, y = j}) and "-" or "*")..i.."  "
			if start and start.x == i and start.y == j then
				line = line.."A".."  "
			elseif endpos and endpos.x == i and endpos.y == j then
				line = line.."B".."  "
			elseif path and self:containGrid(path, {x = i, y = j}) then
				line = line.."+".."  "
			else
				line = line..(self:getGridCanMove({x = i, y = j}) and "-" or "*").."  "
			end
		end
		print(line)
	end
	print("-------- AStar:debug --------")
end

return AStar